#include <bits/stdc++.h>   
using namespace std; 
int n,k,fal,max_;//fal是答案出错标记，方便快速结束循环
int a[15][15],sum[15][15];//a是原数组，sum是累加数组
bool col[15],cnt[15],temp[15];
bool check(int m){
    if(m<max_)return false;//特判
//第一个循环是对每种横刀状态进行遍历（每一个i都代表一种横刀状态）
    for(int i=0;i<(1<<(n-1));i++){
        fal=0;//更新此种横刀状态为正确，内部循环发现是因横刀出错时就一头冲出来
        memset(col,0,sizeof(col));
        memset(cnt,0,sizeof(cnt));
        memset(temp,0,sizeof(temp));
        vector<int> v;
        int count=0,ans=0, tmp=i;
        while(tmp){
            count++;
            if(tmp&1){//获取i中1的位置，存入这种状态下的每个横刀位置
                v.push_back(count);//v用来存横刀位置，若v里面为1,3,4，加入n后，表示横刀区间1-1，2-3，4-4，5-n
                ans++;
            }
            tmp/=2;
        }
        if(ans>k)continue;//特判
        v.push_back(n);
        int p=0,top=1,down;//top是该区间最上面元素位置,down是此横刀位置,p为当前的第几个横刀区间（
//第二个循环是切竖刀的，在每个竖位置遍历列区间，一旦某个横刀区间加上这个列超过答案就说明可以切竖刀了
        for(int j=1;j<=n;j++){
            p=0,top=1;//每切一次竖刀就重置一次
//第三个循环是遍历横刀区间的（我们要自上而下遍历每个区间）
            for(int x:v){//用x来访问v中的所有元素，取出每个横刀位置
                down=x;
                int now=get_sum(top,j,down,j);//求列区间和（列宽为1）
                if(now>m){//如果仅列区间已经大于答案就说明是横刀状态失误了，fal标记一下，直接冲到最外面
                    fal=1; break;
                }
//求新的横刀区间（原横刀区间加列区间）
                cnt[++p]+=now;//将上个区间加上这个区间
                if(col[j-1]){
                    cnt[p]=now;//上个位置被切过了，就说明我们不应该加的
                }
                temp[p]=now;//temp存每个列区间和
//判断该横刀区间，决策是否切竖刀
                if(cnt[p]>m){//该区间和大于答案，说明要切竖着在j-1的位置一刀，cnt再从第j列开始计算和（你只有犯错的时候才知道自己犯错了）
                    col[j-1]=1;//更新竖切的位置和区间和
                    cnt[p]=now;
                    for(int ii=1;ii<p;ii++)cnt[ii]=temp[ii];//之前的区间也要因此而更新了，用上temp了
                }
                top=down+1;//top是下个区间最上面位置
            }if(fal)break;
        }
        if(fal)continue;
        for(int j=1;j<=n-1;j++)	if(col[j])ans++;//col存放的竖切刀
        if(ans<=k)return true;
    }	return false;
}
int main() {
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
			max_=max(max_,a[i][j]);
			sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];//累加
		}
		int l=0,r=2000*15*15;
		while(l<=r)
		{
			int mid=(l+r)>>1;//二分
			if(check(mid)) r=mid-1;//判断是否满足条件
			else l=mid+1;
		}
		cout<<l<<"\n";
	}
	return 0;
}
